public class MyLinkedList {
    class ListNode {
        public int val;  //值域
        public ListNode next; //指针域 (初值为null)
        public ListNode(int val) {
            this.val = val;
        }
    }
    ListNode head; //头指针
    public int size() {
        ListNode p = head;
        int count = 0;
        while (p != null) {
            count ++;
            p = p.next;
        }
        return count;
    }

    public void addLast(int val) {  //模拟实现addLast (尾插)
        ListNode newNode = new ListNode(val);
        if (head == null) {
            head = newNode;
        } else{
            ListNode p = head;
            while (p.next != null) {  //找尾结点
                p = p.next;
            }
            p.next = newNode;
        }
    }

    public boolean addFirst(int val) {  //模拟实现addFirst (头插)
        if (head == null) {
            return false;
        }
        ListNode newNode = new ListNode(val);
        newNode.next = head;
        head = newNode;
        return true;
    }

    public boolean addIndex(int index, int val) {  //模拟实现addIndex (在指定位置插入)
        if (index < 0 || index > size()) {
            System.out.println("输入的下标有误, 请检查");
            return false;
        }
        if (head == null) {
            return false;
        }
        ListNode newNode = new ListNode(val);
        // 找到index位置的前一个
        ListNode TargetPreviousNode = head;
        int stepCount = index-1;
        while (stepCount !=0) {
            TargetPreviousNode = TargetPreviousNode.next;
            stepCount--;
        }
        ListNode TargetNode = TargetPreviousNode.next;

        //添加节点
        TargetPreviousNode.next = newNode;
        newNode.next = TargetNode;

        return true;
    }


    public boolean removeLast() { //模拟实现removeLast (尾删)
        // 判空
        if (head == null) {
            return false;
        }
        // 找到尾结点的前一个节点
        ListNode p = head;
        while (p.next.next != null) {
            p = p.next;
        }
        p.next = null; // 删除尾结点
        return true;
    }
    public boolean removeFirst() {  //模拟实现removeLast (头删)
        //判空
        if (head == null) {
            return false;
        }
        //
        ListNode p = head.next; //p指向头结点的下一个结点.
        head.next = null;
        head = p;
        return true;
    }

    public boolean removeIndex(int index) {  //模拟实现removeIndex (删除指定位置的元素)
        if (head == null) {
            return false;
        }
        ListNode TargetPreviousNode = head;
        int stepCount = index-1;
        while (stepCount != 0) { //找到目标节点的前一个节点
            TargetPreviousNode = TargetPreviousNode.next;
        }
        ListNode TargetNode = TargetPreviousNode.next;

        // 删除目标节点
        TargetPreviousNode.next = TargetNode.next;
        TargetNode.next = null; // 给要删除节点的next域置空.

        return true;
    }
    public boolean removeKey(int data) {  //模拟实现removeKey (删除指定定值的元素)
        if (head == null) {
            return false;
        }
        int flag = 0;
        ListNode TargetPreviousNode = head;
        while (TargetPreviousNode.next != null) {
            if (TargetPreviousNode.next.val == data) {  //定位要删除节点的前一个节点
                ListNode TargetNode  = TargetPreviousNode.next;
                TargetPreviousNode.next = TargetNode.next;
                TargetNode.next = null;

                flag = 1;
            }
            TargetPreviousNode = TargetPreviousNode.next;
            if (TargetPreviousNode != null) {
                continue;
            } else {
                break;
            }
        }
        if (flag == 1) {  //删除成功
            return true;
        }
        return false;  //没有 val == data 的结点
    }

    public boolean contains(int val) {  //模拟实现contains (是否包含某一元素)
        ListNode p = head;
        while (p != null) {
            if (p.val == val) {
                return true;
            }
            p = p.next;
        }
        return false;
    }

    public boolean isEmpty() {  //判断当前链表是否为空
        if(head == null) {
            return true;
        }
        return false;
    }

    public void clear() {  //清空链表
        head = null;
    }

    @Override
    public String toString() {
        String str = "";
        ListNode p = head;
       while(p != null) {
            if (p == head){
                str += "[";
                str += head.val;
                str += ",";
                p = p.next;
                continue;
            }
            if (p.next == null) {
                str += p.val;
                str += "]";
                p = p.next;
                continue;
            }
            str += p.val;
            str += ",";
            p = p.next;
        }
        return str;
    }
}
